package com.sheng.leetcode.year2023.month11.day29;

import org.junit.Test;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author by ls
 * @date 2023/11/30
 * <p>
 * 2336. 无限集中的最小数字<p>
 * <p>
 * 现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。<p>
 * 实现 SmallestInfiniteSet 类：<p>
 * SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。<p>
 * int popSmallest() 移除 并返回该无限集中的最小整数。<p>
 * void addBack(int num) 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集最后。<p>
 * <p>
 * 示例：<p>
 * 输入<p>
 * ["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]<p>
 * [[], [2], [], [], [], [1], [], [], []]<p>
 * 输出<p>
 * [null, null, 1, 2, 3, null, 1, 4, 5]<p>
 * 解释<p>
 * SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();<p>
 * smallestInfiniteSet.addBack(2);    // 2 已经在集合中，所以不做任何变更。<p>
 * smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。<p>
 * smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。<p>
 * smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。<p>
 * smallestInfiniteSet.addBack(1);    // 将 1 添加到该集合中。<p>
 * smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，<p>
 * // 且 1 是最小的整数，并将其从集合中移除。<p>
 * smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。<p>
 * smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。<p>
 * <p>
 * 提示：<p>
 * 1 <= num <= 1000<p>
 * 最多调用 popSmallest 和 addBack 方法 共计 1000 次<p>
 */
public class LeetCode2336 {

    @Test
    public void test01() {
        SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
        smallestInfiniteSet.addBack(2);    // 2 已经在集合中，所以不做任何变更。
        System.out.println(smallestInfiniteSet.popSmallest()); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。
        System.out.println(smallestInfiniteSet.popSmallest()); // 返回 2 ，并将其从集合中移除。
        System.out.println(smallestInfiniteSet.popSmallest()); // 返回 3 ，并将其从集合中移除。
        smallestInfiniteSet.addBack(1);    // 将 1 添加到该集合中。
        System.out.println(smallestInfiniteSet.popSmallest()); // 返回 1 ，因为 1 在上一步中被添加到集合中，且 1 是最小的整数，并将其从集合中移除。
        System.out.println(smallestInfiniteSet.popSmallest()); // 返回 4 ，并将其从集合中移除。
        System.out.println(smallestInfiniteSet.popSmallest()); // 返回 5 ，并将其从集合中移除。
    }
}

class SmallestInfiniteSet {

    /**
     * 集合中存放从无限集中移除的正整数
     */
    Queue<Integer> list;

    /**
     * 集合中的最小元素
     */
    int n;

    /**
     * 初始化 SmallestInfiniteSet 对象以包含 所有 正整数
     */
    public SmallestInfiniteSet() {
        list = new PriorityQueue<>();
        n = 1;
    }

    /**
     * 移除 并返回该无限集中的最小整数
     *
     * @return 无限集中的最小整数
     */
    public int popSmallest() {
        // 最小整数
        Integer poll = n;
        // 将该整数添加到集合中
        list.add(n);
        // 找到下一个最小整数
        int num = n + 1;
        while (list.contains(num)) {
            num++;
        }
        n = num;
        return poll;
    }

    /**
     * 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集最后
     *
     * @param num
     */
    public void addBack(int num) {
        if (list.contains(num)) {
            // 集合中存在 num 时，将 num 移除
            list.remove(num);
            // 计算最小整数
            n = Math.min(n, num);
        }
    }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.popSmallest();
 * obj.addBack(num);
 */
